"""
时间复杂度：
    - O(nlogn)
空间复杂度：
    - O(n)
"""
import random

from SortingAlgorithm.cal_time.cal_time import cal_time


# 归并排序
@cal_time(name="归并排序时间")
def merge_sort(lst):
    _merge_sort(lst)


def _merge_sort(lst):
    mid = len(lst) // 2
    if len(lst) <= 1:
        return lst
    # left 采用合并后形成的有序的新的列表
    lst_l = _merge_sort(lst[:mid])

    # right 采用合并后形成的有序的新的列表
    lst_r = _merge_sort(lst[mid:])
    # 将两个有序列合并为一个新的整体
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(lst_l) and right_pointer < len(lst_r):
        if lst_l[left_pointer] <= lst_r[right_pointer]:
            result.append(lst_l[left_pointer])
            left_pointer += 1
        else:
            result.append(lst_r[right_pointer])
            right_pointer += 1
    result += lst_l[left_pointer:]
    result += lst_r[right_pointer:]
    return result


if __name__ == "__main__":
    li = list(range(10000))
    random.shuffle(li)


    merge_sort(li)
